package leetcode41_50;

import org.junit.Test;

import java.util.*;

/**
 * @author shhjiang_001
 * @create 2020-06-17 22:35
 */

        /*
        给定一个可包含重复数字的序列，返回所有不重复的全排列。
        示例:

        输入: [1,1,2]
        输出:
        [
        [1,1,2],
        [1,2,1],
        [2,1,1]
        ]
        */

public class Solution47 {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int pos = 0;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        HashSet<Integer> set = new HashSet<>();
        method(nums,pos,deque,set);
        return list;
    }

    private void method(int[] nums, int pos, ArrayDeque<Integer> list1, HashSet<Integer> set) {
        if (pos > nums.length-1){
                list.add(new ArrayList<>(list1));
            return;
        }
        for (int i = 0;i<nums.length;i++){
            if (!set.contains(i)){
                if (i>0 && nums[i]==nums[i-1] &&set.contains(i-1)){
                    break;
                }
                set.add(i);
                list1.add(nums[i]);
                method(nums,pos+1,list1, set);
                list1.removeLast();
                set.remove(i);
            }

        }
    }
    @Test
    public void test() {
        Solution47 solution47 = new Solution47();
//        System.out.println(Arrays.asList(new int[]{1, 2, 3}).toString());
        solution47.permuteUnique(new int[]{1,1,2});
    }
}
